#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
void ShellSort(int *a,int n)
{
	int gap=n;
	while(gap>1)
	{
		gap=gap/3+1;
		for(int i=gap;i<=n-1;i++)
		{
			int end=i-gap;
			int tmp=a[i];
			while(end>=0)
			{
				if(a[end]>tmp)
				{
					a[end+gap]=a[end];
					end-=gap;
				}
				else
				{
					break;
				}
			}
			a[end+gap]=tmp;
		}
	}
}
void Swap(int* p1,int* p2)
{
	int tmp=*p1;
	*p1=*p2;
	*p2=tmp;
}
void SelectSort(int *a,int n)
{
	int left=0;
	int right=n-1;
	while(left<right)
	{
		int maxi=left;
		int mini=left;
		for(int i=left;i<=right;i++)
		{
			if(a[maxi]<a[i])
			{
				maxi=i;
			}
			if(a[mini]>a[i])
			   mini=i;
		}
		Swap(&a[mini],&a[left]);
		if(left==maxi)
		{
			maxi=mini;
		}
		Swap(&a[maxi],&a[right]);
		left++;
		right--;
	}
}
//void QuickSort1(int* a,int left,int right)
//{
//	if(left>=right)
//	{
//		return ;
//	}
//	int keyi=left;
//	int begin=left;
//	int end=right;
//	while(begin<end)
//	{
//		while(begin<end && a[end]>=a[keyi])
//		{
//			end--;
//		}
//		while(begin<end && a[begin]<=a[keyi])
//		{
//			begin++;
//		}
//		Swap(&a[begin],&a[end]);
//	
//	}
//	Swap(&a[begin],&a[keyi]);
//	keyi=begin;
//	QuickSort1(a,left,keyi-1);
//	QuickSort1(a,keyi+1,right);
//
//}

int MidNum(int* a,int left,int right)
{
	int mid=(left+right)/2;
	if(a[mid]<a[left])
	{
		if(a[right<a[mid]])
		{
			return mid;
		}
		else
		{
			if(a[left]>a[right])
			{
				return right;
			}
			else
			{
				return left;
			}
		}
	}
	else//a[mid]>=a[left]
	{
		if(a[right]>a[mid])
		{
			return mid;
		}
		else
		{
		    if(a[left]>a[right])
			{ 
			     return left;
			}	
			else
			{
				return right;
			}
		}
	}
}
void QuickSort1(int* a,int left,int right)
{
	if(left>=right)
	{
		return ;
	}
	int begin=left;
	int end=right;
	int keyi=MidNum(a,left,right);
	Swap(&a[keyi],&a[begin]);
	keyi=begin;
	while(begin<end)
	{
		while(begin<end && a[end]>=a[keyi])
		{
			end--;
		}
		while(begin<end && a[begin]<=a[keyi])
		{
			begin++;
		}
		Swap(&a[begin],&a[end]);
	}
	Swap(&a[begin],&a[keyi]);
	keyi=begin;//当一边只有1个或0个时这一边就结束了
	QuickSort1(a,left,keyi-1);
	QuickSort1(a,keyi+1,right);
	

}
void QuickSort2(int *a,int left,int right)
{
	if(left>=right)
	{
		return ;
	}
	int keyi=left;
	int prev=left;
	int cur=left+1;
	while(cur<=right)
	{
		if(a[cur]<=a[keyi])
		{
			prev++;
			if(prev!=cur)
			{
				Swap(&a[prev],&a[cur]);
			}
			cur++;
		}
		else
		{
			cur++;
		}
		
	}
	Swap(&a[prev],&a[keyi]);
	keyi=prev;
	QuickSort2(a,left,keyi-1);
	QuickSort2(a,keyi+1,right);
	

}
void BubbleSort(int*a,int n)
{
	for(int i=n-2;i>=0;i--)
	{
		for(int j=0;j<=i;j++)
		{
			if(a[j]>a[j+1])
			{
				Swap(&a[j],&a[j+1]);
			}
		}
	}
}
void AdjustDown(int *a,int n,int i)
{
	int parent=i;
	int child=i*2+1;
	while(child<=n-1)
	{
		if(child+1<=n-1 && a[child+1]>a[child])
		{
			child++;
		}
		if(a[child]>a[parent])
		{
			Swap(&a[child],&a[parent]);
		}
		else
		{
			break;
		}
		
		parent=child;
		child=child*2+1;
	}
}
void HeapSort(int*a,int n)
{
	for(int i=(n-1-1)/2;i>=0;i--)
	{
		AdjustDown(a,n,i);
	}
	
	
	/*int tmpi=n-1;
	while(tmpi>=1)
	{
		Swap(&a[0],&a[tmpi]);
		tmpi--;
		AdjustDown(a,tmpi+1,0);
	}*/
	
	
	for(int i=n-1;i>=1;i--)
	{
		Swap(&a[i],&a[0]);
		AdjustDown(a,i,0);
	}
}

void _MergeSort(int* a,int left,int right,int *tmp)
{
	if(left==right)
	{
		return ;
	}

	int midi=(left+right)/2;
	_MergeSort(a,left,midi,tmp);
	_MergeSort(a,midi+1,right,tmp);
	
	int begin1=left,end1=midi,begin2=midi+1,end2=right;
	int j=left;
	while(begin1<=end1 && begin2<= end2)
	{
		if(a[begin1]<=a[begin2])
		{
			tmp[j]=a[begin1];
			begin1++;
			j++;
		}
		else
		{
			tmp[j]=a[begin2];
			begin2++;
			j++;
		}
	}
	
	while(begin1<=end1)
	{
		tmp[j++]=a[begin1++];
	}
	
		while(begin2<=end2)
	{
		tmp[j++]=a[begin2++];
	}
	memcpy(a+left,tmp+left,sizeof(int)*(right-left+1) );
	
	
	
	
}
void MergeSort(int*a,int left,int right)
{
	int* tmp=(int*)malloc((right-left+1)*sizeof(int));
	_MergeSort(a,left,right,tmp);
	free(tmp);
	tmp=NULL;
}

void CountSort(int* a,int n)
{
	int* tmp=(int*)calloc(n,sizeof(int));
	int min=a[0],max=a[0];
	for(int i=0;i<n;i++)
	{
		if(a[i]<min)
		{
			min=a[i];
		}
		if(a[i]>max)
		{
			max=a[i];
		}
	}
	for(int i=0;i<n;i++)
	{
		tmp[a[i]-min]++;
	}
	int j=0;
	for(int i=0;i<n;i++)
	{
		while(tmp[i]--)
		{
			a[j]=i+min;
			j++;
		}
	}
	free(tmp);
}
typedef int STDatatype;
typedef struct stack{
	STDatatype* a;
	int top;//top就是元素个数，当0个元素时top为0
	int capacity;
}stack;

void StackInit(stack* ps)
{
	assert(ps);
	ps->a=NULL;
	ps->capacity=ps->top=0;
}

void StackPush(stack* ps,STDatatype x)
{
	assert(ps);
	if(ps->top==ps->capacity)
	{
		int newcapacity=ps->capacity==0 ?4:2*ps->capacity;
		int* tmp=(int*)realloc(ps->a,newcapacity*sizeof(int));//BUG--没乘类型大小
		if(tmp==NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->a=tmp;
		ps->capacity=newcapacity;
	}
	ps->a[ps->top]=x;
	(ps->top)++;
}

void StackPop(stack* ps)
{
	assert(ps);
	if(ps->top!=0)
	{
		ps->top--;
	}
	else
	{
		perror("ps->top==0");
	}
}

bool StackEmpty(stack * ps)
{
	return ps->top==0;
}

STDatatype StackTop(stack* ps)
{
	assert(ps);
	return ps->a[ps->top-1];
}

void StackDestroy(stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->capacity=ps->top=0;
}

void QuickSortNonR(int *a,int left,int right)
{
	stack ST;
	StackInit(&ST);

	StackPush(&ST,right);
	StackPush(&ST,left);
	while(!StackEmpty(&ST))
	{
		int begin=StackTop(&ST);//end 和begin是每个小区间的起始和末尾
	//	int tmp1=begin;
		StackPop(&ST);
		int end=StackTop(&ST);
	//	int tmp2=end;
		StackPop(&ST);
		
		int keyi=begin;
		int cur=begin+1;
		int prev=begin;
		
//		while(tmp1<tmp2)
//		{
//			while(tmp1<tmp2 && a[tmp2]>=a[keyi])
//			{
//				tmp2--;
//			}
//			while(tmp1<tmp2 && a[tmp1]<=a[keyi])
//			{
//				tmp1++;
//			}
//			Swap(&a[tmp1],&a[tmp2]);
//		}
//		Swap(&a[keyi],&a[tmp1]);
//		keyi=tmp1;
//		if(keyi<=end-2)
//		{
//			StackPush(&ST,end);
//			StackPush(&ST,keyi+1);
//
//		}
//		if(keyi>=begin+2)
//		{
//			StackPush(&ST,keyi-1);
//			StackPush(&ST,begin);
//		}
   
          while(cur<=end)
          {
          	  if(a[cur]<a[keyi] && ++prev!=cur)
          	  {
          		  Swap(&a[prev],&a[cur]);
			  }
			  cur++;
			  
		  }
		  Swap(&a[keyi],&a[prev]);
		  keyi=prev;
		  
		  if(keyi<=end-2)
		  {
		  	StackPush(&ST,end);
		  	StackPush(&ST,keyi+1);
		  }
		  
		  if(keyi>=begin+2)
		  {
		  			  	StackPush(&ST,keyi-1);
		  	  StackPush(&ST,begin);
		  }
	}
	StackDestroy(&ST);
	
}
void MergeSortNonR(int*a,int n)
{
	int * tmp=(int*)malloc(sizeof(int)*n);
	int gap=1;
	while(gap<n)
	{
		for(int i=0;i<n;i+=2*gap)
		{
			int begin1=i,end1=i+gap-1,begin2=end1+1,end2=begin2+gap-1;
			int j=i;
			if(end1>=n-1)
			{
				break;
			}
			
			if(end2>=n)
			{
				end2=n-1;
			}
			
			while(begin1<=end1 && begin2<=end2)
			{
				if(a[begin1]<a[begin2])
				{
					tmp[j++]=a[begin1++];
				}
				else
				{
					tmp[j++]=a[begin2++];
				}
			}
			
			while(begin1<=end1)
			{
				tmp[j++]=a[begin1++];
			}
			
			while(begin2<=end2)
			{
				tmp[j++]=a[begin2++];
			}
			
			memcpy(a+i,tmp+i,sizeof(int)*(end2-i+1));
		}
		gap*=2;
	}
}
int main()
{
	int a[10]={1,5,9,8,7,4,6,3,2,8};
	//ShellSort(a,10);
	//SelectSort(a,10);
	QuickSort1(a,0,9);
	//QuickSort2(a,0,9);
	//BubbleSort(a,10);
	//HeapSort(a,10);
	//MergeSort(a,0,9);
	//CountSort(a,10);
	//QuickSortNonR(a,0,9);
	//MergeSortNonR(a,10);
	for(int i=0;i<10;i++)
	{
		printf("%d ",a[i]);
	}
	
	return 0;
}